#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}


// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}       


// 层序遍历
void levelorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        printf("%d ", node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}



int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    printf("Tree traversal in pre-order:\n");
    preorderTraversal(root);

    printf("\nTree traversal in in-order:\n");
    inorderTraversal(root);

    printf("\nTree traversal in post-order:\n");
    postorderTraversal(root);

    printf("\nTree traversal in level-order:\n");
    levelorderTraversal(root);

    return 0;
}

